///###############
//FILE          : BinarySearchTree.java
//WRITER        : Lior Zimmerman, liorz06, 066462300
//WRITER        : Ohad Dan, ohad_dan, 036767960
//EXERCISE      : oop ex1 2008
//DESCRIPTION   : this class implements a sorted BinarySearchTree
//###############
package oop.ex1.sortedStructure;
import java.util.List;
import java.util.ArrayList;
/**
 * This class represents a binary search tree data structure.
 * @author liorz06
 * @author ohad_dan
 *
 * @param <Key>
 * @param <InfoType>
 */
class BinarySearchTree
<Key extends Comparable<Key>,  InfoType extends Keyed<Key> > 
implements  SortedStructure<Key, InfoType> {

    //represents the root node.
	protected BinaryNode<InfoType> _root;
	int _size;
/**
 * This class represents the node of the binary search tree.
 * @author liorz06
 * @author ohad.dan
 * @param <Info>
 */
	private class BinaryNode<Info> {
		  //***********************************************
		  // Data Members :                               * 
		  //*********************************************** 
		  	InfoType _data;
	        BinaryNode<Info> _leftSon;
	        BinaryNode<Info> _rightSon;
	        BinaryNode<Info> _father;

	        //*********************************************
	        // Methods :                                  * 
	        //*********************************************
	        /**
	         * Constructs an empty new BinaryNode.
	         */
	        public BinaryNode() {
	            _data=null;
	        }
	        /**
	         * Constructs a new BinaryNode that holds the given data.
	         * @param data Data held by the node.
	         */
	        public BinaryNode(InfoType data){
	            _data = data;
	        }
	        /**
	         * Constructs a new BinaryNode that holds the given data,
	         * and sets it's father.
	         * @param data Data held by the node.
	         * @param father Father of the node.
	         */
	        public BinaryNode(InfoType data,BinaryNode<Info> father){
	            _data = data;
	            this.setFather(father);

	        }
	        /**
	         * Sets the father of the node to be the given node.
	         * @param father Node to be set as father
	         */
	        void setFather(BinaryNode<Info> father) {
	            _father = father;
	        }
	        /**
	         * Sets the left son to be the given node.
	         * @param leftSon Node to be set as left son.
	         */
	        void setLeftSon(BinaryNode<Info> leftSon) {
	        	_leftSon = leftSon;
	        }
	        /**
	         * Sets the right son to be the given node.
	         * @param rightSon Node to be set as right son.
	         */
	        void setRightSon(BinaryNode<Info> rightSon) {
	        	_rightSon = rightSon;
	        }
	        /**
	         * Returns the right son.
	         * @return The right son.
	         */
	        BinaryNode<Info> getRightSon() {
	            return _rightSon;
	        }
	        /**
	         * Returns the left son.
	         * @return The left son.
	         */
	        BinaryNode<Info> getLeftSon() {
	            return _leftSon;
	        }
	        /**
	         * Returns node's father.
	         * @return Node's father.
	         */
	        BinaryNode<Info> getFather() {
	            return _father;
	        }
	        /**
	         * Returns Node's data.
	         * @return Node;s data.
	         */
	        InfoType getData() {
	            return _data;
	        }
	        void setData( InfoType data ) {
	            _data = data;
	        }
	    }
	
	//*****************************************************
	// Public Methods :                                   * 
	//*****************************************************
    
	/**
	 * Constructs an empty binary tree.
	 */
	public BinarySearchTree(){
		_root = null;
		_size = 0;
	}
	
   /**
    * Returns true if the list is empty, false otherwise.
    * @return True if the list is empty, false otherwise.
    */
	public boolean  isEmpty(){
    	return (_root == null);
    }
	/**
	 * Returns the size of the tree - number leaves.
	 * @return Tree size.
	 */
    public int size(){ 
    	return _size;
    }
    /**
     * Inserts new data.
     * @param data - data to be inserted.
     */
    public void insert(InfoType data) throws SortedStructureNullException, 
    SortedStructureDuplicateException{
    	//if the data is null, throw an exception
        if ( data == null ) {
            throw new SortedStructureNullException("Null Value inserted");
        }
        if ( _root == null ) {
            _root = new BinaryNode<InfoType>(data);
            _size++;
            return;
        }
        insert(_root,data,null);
        _size++;
    }    
    /**
     * Insert recursively the given data to it's place. 
     * @param currentNode The current checked node
     * @param data The data to be inserted.
     * @param parent The parent of the current checked node.
     */
    private void insert(BinaryNode<InfoType> currentNode,
    		InfoType data,BinaryNode<InfoType> parent) throws
    		SortedStructureDuplicateException,SortedStructureNullException {
    	if (currentNode == null){
    		currentNode = new BinaryNode<InfoType>(data,parent);
    		if( parent.getData().getKey().compareTo(data.getKey()) > 0 ) {
    		    parent.setLeftSon(currentNode);
    		}else { parent.setRightSon(currentNode); }
    		currentNode.setFather(parent);
    	}
    	else{
   		if (data.getKey().equals(currentNode.getData().getKey())){
    			throw new 
                SortedStructureDuplicateException(
                        "Can't insert identical keys");
    		}
    		if (currentNode.getData().getKey().compareTo(data.getKey()) > 0){
    		    insert(currentNode.getLeftSon(),data,currentNode);
    		}
    		else{
    			insert(currentNode.getRightSon(),data,currentNode);
    		}
    	}
    }
    /**
     * Retrieves data holds the given key.
     * @param key The key of the desired data.
     */
    public InfoType get (Key key){
        if ( key == null ) {
            return null;
        }
        return get( key, _root);
    }
    /**
     * Returns recursively the binary node with the provided key.
     * @param key The key of the desired data.
     * @param node Current inspected node.
     * @return The node with the given key.
     */
    private BinaryNode<InfoType> getBinaryNode( Key key, 
            BinaryNode<InfoType> node ){
        if ( node == null ) { return null; }
        if( node.getData().getKey().equals(key) ) {
            return node;
        }
        BinaryNode<InfoType> holder;
        if( node.getData().getKey().compareTo(key) > 0 ) {
             holder = getBinaryNode(key, node.getLeftSon() );
        }else { holder = getBinaryNode( key, node.getRightSon() ); }
        return holder;
    }
    /**
     * Returns the data of the node with given key.
     * @param key Key of the desired data.
     * @param node Search under this node subtree.
     * @return Data of node with given key.
     */
    private InfoType get( Key key, BinaryNode<InfoType> node ) {
        BinaryNode<InfoType> returnNode = getBinaryNode(key, node);
        if ( returnNode == null ) { 
            return null;
        }
        return returnNode.getData();
        
    }
    /**
     * Removes the given object.
     * @param key The key of the node that will br removed.
     * @return The removed object.
     */

    public InfoType remove (Key key){
        if ( key == null ) {
            return null;
        }
        BinaryNode<InfoType> target = getBinaryNode(key, _root);
        
        if( target == null ) {
            return null;
        }
    	InfoType data = target.getData();
    	delete(target);
    	if ( data != null ) {
    	    _size--;
    	}
    	return data;
    }
    /**
     * Deletes a node with one child.
     * @param node The node to be deleted.
     */
    private void deleteOneChild( BinaryNode<InfoType> node ) {
        BinaryNode<InfoType> father = node.getFather();
        if ( father != null ) {
            if ( father.getLeftSon() == node ) {
                father.setLeftSon(null);
            }else { father.setRightSon(null); }
        }
        else {
            _root = null;
        }
    }
    /**
     * Return the only child of the given node.
     * @param node A node with one child.
     * @return The only child of the given node.
     */
    private BinaryNode<InfoType> returnOnlyChild( BinaryNode<InfoType> node) {
        if ( node.getLeftSon() != null ) {
            return node.getLeftSon();
        }
        return node.getRightSon();
    }
    /**
     * Returns the node with minimum data value in the given subtree.
     * @param node Range of check is in this node subtree.
     * @return The node with the minimum data value.
     */
    private BinaryNode<InfoType> minNode( BinaryNode<InfoType> node ){
        while ( node.getLeftSon() != null ){
            node = node.getLeftSon();
        }
        return node;
    }
    /**
     * Replaces one node with another.
     * @param newNode The new node.
     * @param node The node to be replaced.
     */
    private void replaceNode( BinaryNode<InfoType> newNode, 
            BinaryNode<InfoType> node ) {
        newNode.setFather(node.getFather());
        if ( node.getFather() == null ) {
            _root = newNode;
            return;
        }
        if( node.getFather().getLeftSon() == node ) {
            node.getFather().setLeftSon(newNode);
        }else {
            node.getFather().setRightSon(newNode);
        }
        
    }
    /**
     * Deletes a node in the tree.
     * @param node the node to be deleted.
     */
    private void delete( BinaryNode<InfoType> node ) {
        if ( node.getLeftSon() == null && node.getRightSon() == null)  {
            deleteOneChild(node);
            return;
        }
        
        if ( node.getLeftSon() == null || node.getRightSon() == null ) {
            BinaryNode<InfoType> newNode = returnOnlyChild(node);
            replaceNode( newNode, node );
            return;
        }
        
        BinaryNode<InfoType> minChild = minNode(node.getRightSon());
        node.setData(minChild.getData());
        if ( minChild.getRightSon() != null ) {
            minChild.getFather().setRightSon(minChild.getRightSon());
            minChild.getRightSon().setFather(minChild.getFather());
        } else { minChild.getFather().setLeftSon(null); }
    }
        
   /**
    * Returns all the keys of instances found in the tree.
    * @return A list with all the  keys in the tree.
    */
    public List<Key> getAllKeys(){ 
    	return getAllKeysRecurrence( _root );
    }
    /**
     * Recursively returns all the keys in the tree.
     * @param node The current inspected node.
     * @return A list with all the keys in the list.
     */
    private ArrayList<Key> getAllKeysRecurrence( BinaryNode<InfoType> node ) {
    	if ( node == null ) {
    		return new ArrayList<Key>();
    	}
    	ArrayList<Key> leftList = getAllKeysRecurrence(node.getLeftSon());
    	ArrayList<Key> rightList = getAllKeysRecurrence(node.getRightSon());
    	ArrayList<Key> totalList = new ArrayList<Key>();
    	totalList.addAll(leftList);
        totalList.add(node.getData().getKey());
    	totalList.addAll(rightList);
    	return totalList;
    	
    }
    /**
     * Returns a string represantiation of the tree
     * @return A String with the tree's data 
     */
    public String toString(String sep){    	
        if ( sep == null ) { sep = ","; }
        if ( _root == null ) {
             //Empty tree.
        	 return null;
         }
         else{        
        	 String returnval="";
        	 //Returns one index last - the recursive methods
        	 //adds first seperator in excess.
        	 return recursiveToString(_root,sep,returnval).substring(1);
         }
    }
    /**
     * Returns a string representation of the tree.
     * @return A string representing the tree.
     */
    public String toString(){
    	return "[" + toString(",") + "]";
    }
    /**
     * Recursively returns a string with all tree's sorted data.
     * @param currentNode The node currently checked.
     * @param sep Seperator between datas.
     * @param toString currently accumulated string.
     * @return A string representation of the tree's data.
     */
    private String recursiveToString
    (BinaryNode<InfoType> currentNode,String sep,String toString){
    	if (currentNode == null){
    		return toString;
    	}
    	else{
    		if (currentNode.getLeftSon()!=null){
    			//First add all the smaller-than-this-one values
    			toString = toString +
    			recursiveToString(currentNode.getLeftSon(),sep,toString) + 
    			sep  + currentNode.getData() +
    			recursiveToString(currentNode.getRightSon(),sep,toString);
    			return toString;
    			
    		}
    		else{
    			//Add current data, and all greater on sub tree.
    			return toString + sep + currentNode.getData() +
    			recursiveToString(currentNode.getRightSon(),sep,toString);
    			
    		}
    	}
    }
}